{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #序列化与反序列化二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #design #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #设计 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: Codec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #序列化与反序列化二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。</p>\n",
    "\n",
    "<p>请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。</p>\n",
    "\n",
    "<p><strong>提示: </strong>输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅&nbsp;<a href=\"/faq/#binary-tree\">LeetCode 序列化二叉树的格式</a>。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/15/serdeser.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,null,null,4,5]\n",
    "<strong>输出：</strong>[1,2,3,null,null,4,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中结点数在范围 <code>[0, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 297 题相同：<a href=\"https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/\">https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [xu-lie-hua-er-cha-shu-lcof](https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [xu-lie-hua-er-cha-shu-lcof](https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,null,null,4,5]', '[]', '[1]', '[1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return []\n",
    "\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "\n",
    "        result = []\n",
    "        while len(queue) is not 0:\n",
    "            currNode = queue.pop(0)\n",
    "            if currNode is not None:\n",
    "                result.append(currNode.val)\n",
    "\n",
    "                if currNode.left == None:\n",
    "                    queue.append(None)\n",
    "                else:\n",
    "                    queue.append(currNode.left)\n",
    "\n",
    "                if currNode.right == None:\n",
    "                    queue.append(None)\n",
    "                else:\n",
    "                    queue.append(currNode.right)\n",
    "            else:\n",
    "                result.append(None)\n",
    "\n",
    "        index = len(result) - 1\n",
    "        while result[index] is None:\n",
    "            index = index - 1\n",
    "        result = result[0:index+1]\n",
    "        return result\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        for item in data:\n",
    "            result.append(item)\n",
    "        return result\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if root==None:\n",
    "            return \"\"\n",
    "        queue=collections.deque()\n",
    "        queue.append(root)\n",
    "        res=[]\n",
    "        while queue:\n",
    "            cur=queue.popleft()\n",
    "            if not cur:\n",
    "                res.append('null')\n",
    "            else:\n",
    "                res.append(str(cur.val))\n",
    "                queue.append(cur.left)\n",
    "                queue.append(cur.right)\n",
    "        return ','.join(res)\n",
    "    def deserialize(self, data):\n",
    "        if data==None or data=='':\n",
    "            return None\n",
    "        val_lst=data.split('!')\n",
    "        root=TreeNode(val_lst[0])\n",
    "        id_nxt=1\n",
    "        queue=collections.deque()\n",
    "        while queue:\n",
    "            cur=queue.pop()\n",
    "            if val_lst[id_nxt]!='null':\n",
    "                cur.left=TreeNode(val_lst[id_nxt])\n",
    "                queue.append(cur.left)\n",
    "            id_nxt+=1\n",
    "            if val_lst[id_nxt]!='null':\n",
    "                cur.right=TreeNode(val_lst[id_nxt])\n",
    "                queue.append(cur.right)\n",
    "            id_nxt+=1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                res.append('null')\n",
    "                return\n",
    "            res.append(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return res\n",
    "        \n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "\n",
    "        def dfs(data):\n",
    "            val = data.pop(0)\n",
    "            if val == 'null':\n",
    "                return\n",
    "            root = TreeNode(val)\n",
    "            root.left = dfs(data)\n",
    "            root.right = dfs(data)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return dfs(data)\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.data = None\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.data = root\n",
    "        return '666'\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.data\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return root\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return data\n",
    "    \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return root\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return data\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return root\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return data\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return root\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return data\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        return root\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return root\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return data\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        return root;\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        return data;\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root) -> str:\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = \"\"\n",
    "        if root == None:\n",
    "            return \"None\"\n",
    "        \n",
    "        res += str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        datalist = data.split(',')\n",
    "        dataqueue = collections.deque(datalist)\n",
    "        return self.recursion_deserialize(dataqueue)\n",
    "    \n",
    "    def recursion_deserialize(self, datalist):\n",
    "        root = datalist.popleft()\n",
    "        if root == 'None':\n",
    "            return None\n",
    "        rootnode = TreeNode(root)\n",
    "        rootnode.left = self.recursion_deserialize(datalist)\n",
    "        rootnode.right = self.recursion_deserialize(datalist)\n",
    "\n",
    "        return rootnode\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.res = []\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                self.res.append('#')\n",
    "                return\n",
    "            self.res.append(str(root.val))\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return ','.join(self.res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        data = data.split(',')\n",
    "        def dfs(data):\n",
    "            if data[0] == '#':\n",
    "                data.remove(data[0])\n",
    "                return None\n",
    "            root = TreeNode(int(data[0]))\n",
    "            data.remove(data[0])\n",
    "            root.left = dfs(data)\n",
    "            root.right = dfs(data)\n",
    "            return root\n",
    "        return dfs(data)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.s = []\n",
    "        self.ser_traverse(root)\n",
    "        return ','.join(self.s)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        data = data.split(',')\n",
    "        return self.des_traverse(data)\n",
    "        \n",
    "    \n",
    "    def ser_traverse(self, root):\n",
    "        if not root:\n",
    "            self.s.append('#')\n",
    "            return \n",
    "        self.s.append(str(root.val))\n",
    "        self.ser_traverse(root.left)\n",
    "        self.ser_traverse(root.right)\n",
    "        \n",
    "    def des_traverse(self, data):\n",
    "        if not data:\n",
    "            return None\n",
    "        nodes = data.pop(0)\n",
    "        if nodes == '#':\n",
    "            return None\n",
    "        root = TreeNode(int(nodes))\n",
    "        root.left = self.des_traverse(data)\n",
    "        root.right = self.des_traverse(data)\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return \"\"\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            if cur == None:\n",
    "                for i in range(len(queue)):\n",
    "                    if queue[i] != None:\n",
    "                        res.append(\"null\")\n",
    "                        break\n",
    "                continue\n",
    "            res.append(cur.val)\n",
    "            if cur.left:\n",
    "                queue.append(cur.left)\n",
    "            else:\n",
    "                queue.append(None)\n",
    "            if cur.right:\n",
    "                queue.append(cur.right)\n",
    "            else:\n",
    "                queue.append(None)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"\":\n",
    "            return None\n",
    "        root = TreeNode(data[0])\n",
    "        queue = [root]\n",
    "        data.pop(0)\n",
    "        while data:\n",
    "            cur1 = data.pop(0)\n",
    "            cur1_node = TreeNode(cur1)\n",
    "            pre = queue.pop(0)\n",
    "            if len(data) > 0:\n",
    "                cur2 = data.pop(0)\n",
    "                cur2_node = TreeNode(cur2)\n",
    "                pre.left,pre.right = cur1_node,cur2_node\n",
    "                queue.append(cur1_node)\n",
    "                queue.append(cur2_node)\n",
    "            else:\n",
    "                pre.left = cur1_node\n",
    "                queue.append(cur1_node)\n",
    "            \n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Codec:  \n",
    "    def serialize(self, root):\n",
    "        serializeList = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                serializeList.append(None)\n",
    "                return\n",
    "            serializeList.append(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return str(serializeList)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        deserializeList = data[1:-1].replace(' ','').split(',')\n",
    "        deque = collections.deque(deserializeList)\n",
    "\n",
    "        def build(deque):\n",
    "           if not deque:return\n",
    "           tem = deque.popleft()\n",
    "           if tem == \"None\":return\n",
    "           node = TreeNode(int(tem))\n",
    "           node.left = build(deque)\n",
    "           node.right = build(deque)\n",
    "           return node\n",
    "        return build(deque)\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return \"\"\n",
    "        fifo = [root]\n",
    "        result = []\n",
    "        while len(fifo) > 0:\n",
    "            node = fifo.pop(0)\n",
    "            \n",
    "            if node is None:\n",
    "                result.append(None)\n",
    "            else:\n",
    "                result.append(node.val)\n",
    "            \n",
    "            if node is not None:\n",
    "                fifo.append(node.left)\n",
    "                fifo.append(node.right)\n",
    "        while result[-1] is None:\n",
    "            result.pop()\n",
    "        retStr = \"\"\n",
    "        for e in result:\n",
    "            if e is None:\n",
    "                retStr += \"null,\"\n",
    "            else:\n",
    "                retStr += str(e) + \",\"\n",
    "        return retStr[0:-1]\n",
    " \n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if (len(data) == 0):return None\n",
    "        l = data.split(\",\")\n",
    "        n = len(l)\n",
    "        if n == 0:\n",
    "            return None\n",
    "        root = TreeNode(l[0])\n",
    "        cursor = 1\n",
    "        fifo = [root]\n",
    "        while len(fifo) > 0 and cursor < n:\n",
    "            node = fifo.pop(0)\n",
    "            right, left = None, None\n",
    "            if l[cursor] is not None:\n",
    "                left = TreeNode(l[cursor])\n",
    "                fifo.append(left)\n",
    "            if cursor + 1 < n and l[cursor+1] is not None:\n",
    "                right = TreeNode(l[cursor+1])\n",
    "                fifo.append(right)\n",
    "            cursor += 2\n",
    "            node.right = right\n",
    "            node.left = left\n",
    "    \n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return ''\n",
    "\n",
    "        def recur(node, lst):\n",
    "            if not node:\n",
    "                lst.append('#_')\n",
    "                return\n",
    "            lst.append(str(node.val) + '_')\n",
    "            recur(node.left, lst)\n",
    "            recur(node.right, lst)\n",
    "\n",
    "        res = []\n",
    "        recur(root, res)\n",
    "        return ''.join(res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        from collections import deque\n",
    "        queue = deque(data.split('_')[:-1])\n",
    "\n",
    "        def recur(queue_):\n",
    "            val = queue_.popleft()\n",
    "            if val == '#':\n",
    "                return None\n",
    "            root = TreeNode(int(val))\n",
    "            root.left = recur(queue_)\n",
    "            root.right = recur(queue_)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return recur(queue)\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.res = []\n",
    "        self._preorder(root)\n",
    "        return ','.join(self.res)\n",
    "    \n",
    "    def _preorder(self, root):\n",
    "        if root is None:\n",
    "            self.res.append('null')\n",
    "            return\n",
    "        \n",
    "        self.res.append(str(root.val))\n",
    "        self._preorder(root.left)\n",
    "        self._preorder(root.right)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        self.data = data.split(',')\n",
    "        self.curr = 0\n",
    "        return self._depreorder()\n",
    "\n",
    "    def _depreorder(self):\n",
    "        if self.data[self.curr] == 'null':\n",
    "            self.curr += 1\n",
    "            return None\n",
    "        \n",
    "        root = TreeNode(int(self.data[self.curr]))\n",
    "        self.curr += 1\n",
    "        root.left = self._depreorder()\n",
    "        root.right = self._depreorder()\n",
    "        return root\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        deque = collections.deque([root])\n",
    "        res = []\n",
    "        while(deque):\n",
    "            tmp = deque.popleft()\n",
    "            if tmp:\n",
    "                deque.append(tmp.left)\n",
    "                deque.append(tmp.right)\n",
    "                res.append(tmp.val)\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "\n",
    "        while(res[-1] == None):\n",
    "            res.pop()\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        head = TreeNode(data[0])\n",
    "        i = 1\n",
    "        deque = collections.deque([head])\n",
    "        while(deque):\n",
    "            if i >= len(data):\n",
    "                break\n",
    "            tmp = deque.popleft()\n",
    "            if data[i] != None:\n",
    "                new = TreeNode(data[i])\n",
    "                deque.append(new)\n",
    "                tmp.left = new\n",
    "            i += 1\n",
    "            if i >= len(data):\n",
    "                break\n",
    "            if data[i] != None:\n",
    "                new = TreeNode(data[i])\n",
    "                deque.append(new)\n",
    "                tmp.right = new\n",
    "            i += 1\n",
    "        return head\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"[]\"\n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "        res = []\n",
    "        while que:\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                que.append(node.left)\n",
    "                que.append(node.right) \n",
    "            else:\n",
    "                res.append(\"null\")    \n",
    "        return '[' + ','.join(res) + ']'\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == '[]':\n",
    "            return\n",
    "        vals, i = data[1:-1].split(','), 1\n",
    "        que = collections.deque()\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        que.append(root)\n",
    "        while que:\n",
    "            node = que.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                que.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                que.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "    \n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.res = ''\n",
    "        def dfs(root:TreeNode):\n",
    "            if not root:\n",
    "                self.res += 'None' + ','\n",
    "                return \n",
    "            self.res += str(root.val) + ','\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        data = data.split(',')\n",
    "        def dfs():\n",
    "            a = data.pop(0)\n",
    "            if a == 'None':\n",
    "                return None\n",
    "            root = TreeNode(int(a))\n",
    "            root.left = dfs()\n",
    "            root.right = dfs()\n",
    "            return root\n",
    "        return dfs()\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "        return '[' + ','.join(res) + ']'\n",
    "        \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        if data == \"[]\": return\n",
    "        res, i = data[1:-1].split(','), 1\n",
    "        root = TreeNode(int(res[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if res[i]!=\"null\":\n",
    "                node.left = TreeNode(int(res[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if res[i]!=\"null\":\n",
    "                node.right = TreeNode(int(res[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root: return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else: res.append(\"null\")\n",
    "        return '[' + ','.join(res) + ']'\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if data == \"[]\": return\n",
    "        vals, i = data[1:-1].split(','), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root: return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else: res.append(\"null\")\n",
    "        return '[' + ','.join(res) + ']'\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if data == \"[]\": return\n",
    "        vals, i = data[1:-1].split(','), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root: return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else: res.append(\"null\")\n",
    "        return '[' + ','.join(res) + ']'\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if data == \"[]\": return\n",
    "        vals, i = data[1:-1].split(','), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root: return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else: res.append(\"null\")\n",
    "        return '[' + ','.join(res) + ']'\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if data == \"[]\": return\n",
    "        vals, i = data[1:-1].split(','), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from queue import deque\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root: return \"[]\"\n",
    "        \n",
    "        q = deque([root])\n",
    "        res = []\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                q.append(node.left)\n",
    "                q.append(node.right)\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "        return '['+','.join(res)+']'\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if data == \"[]\" or data ==\"\":\n",
    "            return None\n",
    "        vals, i = data[1:-1].split(\",\"), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if vals[i]!=\"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                q.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i]!=\"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                q.append(node.right)\n",
    "            i += 1\n",
    "        print(root.val)\n",
    "        return root\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "    \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        if not root: return '[]'\n",
    "        que = deque([root])\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            if x:\n",
    "                res.append(str(x.val))\n",
    "                que.append(x.left)\n",
    "                que.append(x.right)\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "        res = '[' + ','.join(res) + ']'\n",
    "        print(res)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\": return\n",
    "        vals = data[1:-1].split(',')\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        que = deque([root])\n",
    "        i = 1\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                x.left = TreeNode(int(vals[i]))\n",
    "                que.append(x.left)\n",
    "            # 等于null的情况不用重复写空节点\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                x.right = TreeNode(int(vals[i]))\n",
    "                que.append(x.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            tmp = stack.pop(0)\n",
    "            if tmp: \n",
    "                res.append(tmp.val)\n",
    "                stack.append(tmp.left)\n",
    "                stack.append(tmp.right)\n",
    "            else: \n",
    "                res.append('null')\n",
    "        return res\n",
    "            \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return \n",
    "\n",
    "        i, l = 1, len(data)\n",
    "        root = TreeNode(data[0])\n",
    "        stack = [root]\n",
    "        while stack and i < len(data):\n",
    "            tmp = stack.pop(0)\n",
    "            if data[i] != 'null':\n",
    "                left = TreeNode(data[i])\n",
    "                stack.append(left)\n",
    "                tmp.left = left\n",
    "            i += 1\n",
    "            if data[i] != 'null':\n",
    "                right = TreeNode(data[i])\n",
    "                tmp.right = right\n",
    "                stack.append(right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        Mylist = list()\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal Mylist\n",
    "            if not node:\n",
    "                Mylist.append('#')\n",
    "                return \n",
    "            \n",
    "            Mylist.append(str(node.val))\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return \",\".join(Mylist)\n",
    "                \n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        Nodes = data.split(',')\n",
    "\n",
    "        def buildTree():\n",
    "            nonlocal Nodes\n",
    "            node_val = Nodes.pop(0)\n",
    "            if node_val == '#':\n",
    "                return None\n",
    "\n",
    "            node = TreeNode(node_val)\n",
    "            node.left = buildTree()\n",
    "            node.right = buildTree()\n",
    "            return node\n",
    "\n",
    "        return buildTree()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return None\n",
    "        output=[]\n",
    "        queue=[]\n",
    "        queue.append(root)\n",
    "        while len(queue)!=0:\n",
    "            item=queue.pop(0)\n",
    "            if item==None:\n",
    "                output.append(None)\n",
    "                continue\n",
    "            output.append(item.val)\n",
    "            queue.append(item.left)\n",
    "            queue.append(item.right)\n",
    "        while output[-1]==None:\n",
    "            output.pop(-1)\n",
    "        if len(output)%2==0:\n",
    "            output.append(None)\n",
    "        return output\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "\n",
    "        if data==None:\n",
    "            return None\n",
    "        for i in range(len(data)):\n",
    "            if data[i]==None:\n",
    "                continue\n",
    "            data[i]=TreeNode(data[i])\n",
    "        node=data.pop(0)\n",
    "        tree=[node]\n",
    "        i=0\n",
    "        while len(data)!=0:\n",
    "            left=data.pop(0)\n",
    "            right=data.pop(0)\n",
    "            tree[i].left=left\n",
    "            tree[i].right=right\n",
    "            tree.append(left)\n",
    "            tree.append(right)\n",
    "            i+=1\n",
    "            while i<len(tree) and tree[i]==None:\n",
    "                i+=1\n",
    "        return tree[0] \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "  def serialize(self, root):\n",
    "    return serialise(root)\n",
    "\n",
    "  def deserialize(self, data):\n",
    "    return deserialise(data)\n",
    "\n",
    "\n",
    "def serialise(root: 'TreeNode'):\n",
    "  ans = []\n",
    "  queue = collections.deque()\n",
    "  queue.append(root)\n",
    "  while queue:\n",
    "    node = queue.popleft()\n",
    "    ans.append(node.val if node else None)\n",
    "    if node:\n",
    "      queue.append(node.left)\n",
    "      queue.append(node.right)\n",
    "  return str(ans)\n",
    "  # '[None]' for empty tree\n",
    "\n",
    "def deserialise(data: str):\n",
    "  nodes = data[1:-1].split(', ')\n",
    "  nodes = [TreeNode(int(x)) if x != 'None' else None for x in nodes]\n",
    "  # 用一个 flag 记录是左边还是右边\n",
    "  # 如果不是 None 就放在 queue 中，作为接下来的 parent\n",
    "  # 每次插入一个 node\n",
    "  head = nodes[0]\n",
    "  queue = collections.deque()\n",
    "  queue.append(head)\n",
    "  left = True\n",
    "  for node in nodes[1:]:\n",
    "    if not queue or not queue[0]:\n",
    "      continue\n",
    "    if left:\n",
    "      queue[0].left = node\n",
    "    else:\n",
    "      queue[0].right = node\n",
    "      queue.popleft()\n",
    "    left = not left\n",
    "    if node:\n",
    "      queue.append(node)\n",
    "  return head\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "\n",
    "        def dfs(rt):\n",
    "            if not rt:\n",
    "                res.append('None')\n",
    "                return\n",
    "            res.append(rt.val)\n",
    "            dfs(rt.left)\n",
    "            dfs(rt.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ','.join(str(v) for v in res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        l = data.split(',')\n",
    "\n",
    "        def dfs(lst):\n",
    "            if not lst:\n",
    "                return None\n",
    "            val = lst[0]\n",
    "            lst.pop(0)\n",
    "            if val == 'None':\n",
    "                return None\n",
    "            root = TreeNode(val)\n",
    "            root.left = dfs(lst)\n",
    "            root.right = dfs(lst)\n",
    "            return root\n",
    "\n",
    "        return dfs(l)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.sb = [] # 装序列化后的元素\n",
    "        self.forward_serialize(root)\n",
    "        return ''.join(self.sb)\n",
    "        \n",
    "    def forward_serialize(self, root):\n",
    "        # 用,分隔元素，用#代表到底部的空节点\n",
    "        if root == None:\n",
    "            self.sb.append('#')\n",
    "            self.sb.append(',')\n",
    "            return\n",
    "        \n",
    "        # 前序位置\n",
    "        self.sb.append(str(root.val))\n",
    "        self.sb.append(',')\n",
    "        # 递归\n",
    "        self.forward_serialize(root.left)\n",
    "        self.forward_serialize(root.right)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        nodes = [] # 装序列拆分出的元素\n",
    "        for i in data.split(','):\n",
    "            nodes.append(i)\n",
    "\n",
    "        return self.forward_deserialize(nodes)\n",
    "\n",
    "    def forward_deserialize(self, nodes):\n",
    "        if len(nodes) == 0:\n",
    "            return None\n",
    "\n",
    "        first = nodes.pop(0)\n",
    "        if first == '#':\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(int(first))\n",
    "        root.left = self.forward_deserialize(nodes)\n",
    "        root.right = self.forward_deserialize(nodes)\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "\n",
    "        def dfs(rt):\n",
    "            if not rt:\n",
    "                res.append('None')\n",
    "                return\n",
    "            res.append(rt.val)\n",
    "            dfs(rt.left)\n",
    "            dfs(rt.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ','.join(str(v) for v in res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        l = data.split(',')\n",
    "\n",
    "        def dfs(lst):\n",
    "            if not lst:\n",
    "                return None\n",
    "            val = lst[0]\n",
    "            lst.pop(0)\n",
    "            if val == 'None':\n",
    "                return None\n",
    "            root = TreeNode(val)\n",
    "            root.left = dfs(lst)\n",
    "            root.right = dfs(lst)\n",
    "            return root\n",
    "\n",
    "        return dfs(l)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return None\n",
    "        d = {}\n",
    "        queue = [(0, root)]\n",
    "        while len(queue) > 0:\n",
    "            loc, node = queue[0][0], queue[0][1]\n",
    "            queue = queue[1:]\n",
    "            d[loc] = node.val\n",
    "            if node.left is not None:\n",
    "                queue.append((2*loc+1, node.left))\n",
    "            if node.right is not None:\n",
    "                queue.append((2*loc+2, node.right))\n",
    "        # print(d)\n",
    "        return d\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data is None:\n",
    "            return None\n",
    "        # print(1 in data)\n",
    "        def create(i):\n",
    "            nonlocal data\n",
    "            if i not in data:\n",
    "                return None\n",
    "            node = TreeNode(data[i])\n",
    "            if 2*i+1 in data:\n",
    "                # print(i, 2*i+1)\n",
    "                node.left = create(2*i+1)\n",
    "            if 2*i+2 in data:\n",
    "                # print(i, 2*i+2)\n",
    "                node.right = create(2*i+2)\n",
    "            return node\n",
    "\n",
    "        return create(0)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        def dfs(root,i):\n",
    "            if not root:\n",
    "                return []\n",
    "            return [[str(i),str(root.val)]]+ dfs(root.left,2*i+1)+ dfs(root.right,2*i+2)\n",
    "        res = dfs(root,0)\n",
    "        res = ['*'.join(i) for i in res]\n",
    "        return ' '.join(res)\n",
    "        \n",
    "    def deserialize(self, data):\n",
    "        if not data:\n",
    "            return None\n",
    "        dic = {}\n",
    "        for line in data.split(' '):\n",
    "            key,val = line.split('*')\n",
    "            dic[int(key)] = int(val)\n",
    "        \n",
    "        def dfs(dic,i):\n",
    "            if i not in dic:\n",
    "                return None \n",
    "            \n",
    "            root = TreeNode(dic[i])\n",
    "            root.left = dfs(dic,2*i+1)\n",
    "            root.right = dfs(dic,2*i+2)\n",
    "            return root\n",
    "        return dfs(dic,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        ans = []\n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "        while stack:\n",
    "            node = stack[-1]\n",
    "            stack.pop(-1)\n",
    "            if node is not None:\n",
    "                ans.append(str(node.val))\n",
    "                stack.append(node.right)\n",
    "                stack.append(node.left)\n",
    "            else:\n",
    "                ans.append('null')\n",
    "        return ','.join(ans)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        vals = data.split(',')\n",
    "\n",
    "        def dfs(i):\n",
    "            if vals[i] == 'null':\n",
    "                return None, i+1\n",
    "            else:\n",
    "                node = TreeNode(int(vals[i]))\n",
    "                node.left, right_start = dfs(i+1)\n",
    "                node.right, end = dfs(right_start)\n",
    "            return node, end\n",
    "        root, _ = dfs(0)\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        def dfs(root,i):\n",
    "            if not root:\n",
    "                return []\n",
    "            return [[str(i),str(root.val)]]+ dfs(root.left,2*i+1)+ dfs(root.right,2*i+2)\n",
    "        res = dfs(root,0)\n",
    "        res = ['*'.join(i) for i in res]\n",
    "        return ' '.join(res)\n",
    "        \n",
    "    def deserialize(self, data):\n",
    "        dic = {}\n",
    "        for line in data.split(' '):\n",
    "            if line:\n",
    "                key,val = line.split('*')\n",
    "                dic[int(key)] = int(val)\n",
    "        \n",
    "        def dfs(dic,i):\n",
    "            if i not in dic:\n",
    "                return None \n",
    "            root = TreeNode(dic[i])\n",
    "            root.left = dfs(dic,2*i+1)\n",
    "            root.right = dfs(dic,2*i+2)\n",
    "            return root\n",
    "        return dfs(dic,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Codec:\n",
    "    def construct(self, cur: TreeNode, node_list: List[str], left_child: List[str],\n",
    "                  right_child: List[str]) -> int:\n",
    "        if cur is None:\n",
    "            return -1\n",
    "        node_list.append(str(cur.val))\n",
    "        cur_index: int = len(node_list) - 1\n",
    "        left_child.append(' ')\n",
    "        right_child.append(' ')\n",
    "        left_index = self.construct(cur.left, node_list, left_child, right_child)\n",
    "        right_index = self.construct(cur.right, node_list, left_child, right_child)\n",
    "        left_child[cur_index] = str(left_index)\n",
    "        right_child[cur_index] = str(right_index)\n",
    "        return cur_index\n",
    "\n",
    "    def serialize(self, root) -> str:\n",
    "        node_list = []\n",
    "        left_child = []\n",
    "        right_child = []\n",
    "        self.construct(root, node_list, left_child, right_child)\n",
    "        a = ' '.join(node_list)\n",
    "        b = ' '.join(left_child)\n",
    "        c = ' '.join(right_child)\n",
    "        return a + '*' + b + '*' + c\n",
    "\n",
    "    def build_tree(self, cur: str, node_list: List[str], left_child: List[str],\n",
    "                   right_child: List[str]) -> TreeNode:\n",
    "        if cur == '':\n",
    "            return None\n",
    "        cur = int(cur)\n",
    "        if cur == -1 or cur >= len(node_list):\n",
    "            return None\n",
    "        cur_node = TreeNode(node_list[cur])\n",
    "        left_node = self.build_tree(left_child[cur], node_list, left_child, right_child)\n",
    "        right_node = self.build_tree(right_child[cur], node_list, left_child, right_child)\n",
    "        cur_node.left = left_node\n",
    "        cur_node.right = right_node\n",
    "        return cur_node\n",
    "\n",
    "    def deserialize(self, data: str):\n",
    "        lists = data.split('*')\n",
    "        a = lists[0]\n",
    "        b = lists[1]\n",
    "        c = lists[2]\n",
    "        print(data)\n",
    "        print(a)\n",
    "        print(b)\n",
    "        print(c)\n",
    "        if a == '':\n",
    "            return None\n",
    "        node_list = a.split(' ')\n",
    "        left_child = b.split(' ')\n",
    "        right_child = c.split(' ')\n",
    "        return self.build_tree('0', node_list, left_child, right_child)\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def serial(self, root: TreeNode) -> None:\n",
    "        \n",
    "        if root is None:\n",
    "            self.arr1.append(str(None))\n",
    "        else:\n",
    "            self.arr1.append(str(root.val))\n",
    "            self.serial(root.left)\n",
    "            self.serial(root.right)\n",
    "    \n",
    "    def serialize(self, root: TreeNode) -> str:\n",
    "        \n",
    "        self.arr1 = []\n",
    "        \n",
    "        self.serial(root)\n",
    "        \n",
    "        return ','.join(self.arr1)\n",
    "    \n",
    "    def deserial(self) -> TreeNode:\n",
    "        \n",
    "        if not self.arr2:\n",
    "            return\n",
    "\n",
    "        if self.arr2[0] == 'None':\n",
    "            self.arr2.popleft()\n",
    "            return\n",
    "\n",
    "        root = TreeNode(self.arr2.popleft())\n",
    "        root.left = self.deserial()\n",
    "        root.right = self.deserial()\n",
    "        \n",
    "        return root\n",
    "            \n",
    "    def deserialize(self, data: str) -> TreeNode:\n",
    "\n",
    "        self.arr2 = deque(data.split(','))\n",
    "\n",
    "        return self.deserial()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"None\"\n",
    "        return str(root.val) + \",\" + self.serialize(root.left) + \",\" + self.serialize(root.right)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        print (data)\n",
    "        datalists = data.split(\",\")\n",
    "        idx = 0\n",
    "        def dfs():\n",
    "            nonlocal idx\n",
    "            if datalists[idx] == \"None\":\n",
    "                idx += 1\n",
    "                return None\n",
    "            root = TreeNode(datalists[idx])\n",
    "            idx += 1\n",
    "            root.left = dfs()\n",
    "            root.right = dfs()\n",
    "            return root\n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return \"\"\n",
    "        queue = [root]\n",
    "        id_map = {}\n",
    "        res = []\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            node = queue[0]\n",
    "            queue = queue[1:]\n",
    "\n",
    "            _id = id_map.setdefault(node, len(id_map))\n",
    "            left_id, right_id = -1, -1\n",
    "            if node.left is not None:\n",
    "                left_id = id_map.setdefault(node.left, len(id_map))      \n",
    "                queue.append(node.left) \n",
    "            if node.right is not None:\n",
    "                right_id = id_map.setdefault(node.right, len(id_map))      \n",
    "                queue.append(node.right) \n",
    "            res.extend((str(_id), str(node.val), str(left_id), str(right_id)))\n",
    "\n",
    "        return \",\".join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        id_map = {}\n",
    "        data = [int(i) for i in data.split(\",\")]\n",
    "        for i in range(0, len(data), 4):\n",
    "            _id, val, l_id, r_id = data[i], data[i+1], data[i+2], data[i+3]\n",
    "            node = id_map.setdefault(_id, TreeNode(0))\n",
    "            node.val = val\n",
    "            node.left = id_map.setdefault(l_id, TreeNode(0)) if l_id >= 0 else None\n",
    "            node.right = id_map.setdefault(r_id, TreeNode(0)) if r_id >= 0 else None\n",
    "\n",
    "        return id_map[0]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"   \n",
    "        if not root:\n",
    "            return \n",
    "        queu=[root]\n",
    "        res=[]\n",
    "        while queu:\n",
    "           \n",
    "            for i in range(len(queu)):\n",
    "                node=queu.pop(0)\n",
    "                if node :\n",
    "                    res.append(str(node.val) )                   \n",
    "                    queu.append(node.left)    \n",
    "                    queu.append(node.right)\n",
    "                else:\n",
    "                    res.append(\"#\")\n",
    "\n",
    "\n",
    "        return res\n",
    "                \n",
    "       \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return      \n",
    "        root=TreeNode(data[0])\n",
    "        queu=[root]\n",
    "        i=1\n",
    "        while queu:\n",
    "            node=queu.pop(0)           \n",
    "            if data[i]!=\"#\":\n",
    "                node.left=TreeNode(data[i])\n",
    "                queu.append(node.left)\n",
    "            i+=1\n",
    "            if data[i]!=\"#\":\n",
    "                node.right=TreeNode(data[i])\n",
    "                queu.append(node.right)\n",
    "            i+=1\n",
    "        return root        \n",
    "      \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return\n",
    "        queu = [root]\n",
    "        res = []\n",
    "        while queu:\n",
    "\n",
    "            for i in range(len(queu)):\n",
    "                node = queu.pop(0)\n",
    "                if node:\n",
    "                    res.append(str(node.val))\n",
    "                    queu.append(node.left)\n",
    "                    queu.append(node.right)\n",
    "                else:\n",
    "                    res.append(\"#\")\n",
    "\n",
    "        return res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return\n",
    "        root = TreeNode(data[0])\n",
    "        queu = [root]\n",
    "        i = 1\n",
    "        while queu:\n",
    "            for _ in range(len(queu)):\n",
    "                node = queu.pop(0)\n",
    "                if data[i] != \"#\":\n",
    "                    node.left = TreeNode(data[i])\n",
    "                    queu.append(node.left)\n",
    "                i += 1\n",
    "                if data[i] != \"#\":\n",
    "                    node.right = TreeNode(data[i])\n",
    "                    queu.append(node.right)\n",
    "                i += 1\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "      \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 导入需要的模块\n",
    "from collections import deque\n",
    "\n",
    "# 创建一个名为 `Codec` 的类\n",
    "class Codec:\n",
    "    # 序列化函数，将二叉树转换为字符串\n",
    "    def serialize(self, root):\n",
    "        # 如果根节点为空，直接返回空字符串\n",
    "        if root is None:\n",
    "            return \"\"\n",
    "        # 创建一个双向队列，并将根节点放入队列\n",
    "        q = deque([root])\n",
    "        # 创建一个空列表用于存储序列化后的节点值\n",
    "        ans = []\n",
    "        while q:\n",
    "            # 从队列中取出节点\n",
    "            node = q.popleft()\n",
    "            if node:\n",
    "                # 如果节点不为空，将节点值添加到答案列表中\n",
    "                ans.append(str(node.val))\n",
    "                # 分别将左子节点和右子节点加入队列\n",
    "                q.append(node.left)\n",
    "                q.append(node.right)\n",
    "            else:\n",
    "                # 如果节点为空，添加 \"#\" 表示空节点\n",
    "                ans.append(\"#\")\n",
    "        # 使用逗号将答案列表中的节点值连接成一个字符串\n",
    "        return \",\".join(ans)\n",
    "\n",
    "    # 反序列化函数，将字符串转换为二叉树\n",
    "    def deserialize(self, data):\n",
    "        # 如果输入数据为空，返回空节点\n",
    "        if not data:\n",
    "            return None\n",
    "        # 将输入数据以逗号为分隔符分割成字符串列表\n",
    "        vals = data.split(\",\")\n",
    "        # 创建根节点，值为第一个字符串\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        # 创建双向队列，并将根节点放入队列\n",
    "        q = deque([root])\n",
    "        i = 1  # 用于迭代字符串列表的索引\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            # 根据字符串列表中的值创建左子节点\n",
    "            if vals[i] != \"#\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                q.append(node.left)\n",
    "            i += 1\n",
    "            # 根据字符串列表中的值创建右子节点\n",
    "            if vals[i] != \"#\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                q.append(node.right)\n",
    "            i += 1\n",
    "        # 返回根节点，即反序列化后的二叉树\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    # 深度遍历\n",
    "    def serialize(self, root):\n",
    "        if not root: return \"None\"\n",
    "        return f\"{root.val} {self.serialize(root.left)} {self.serialize(root.right)}\"\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        def dfs(dl):\n",
    "            val = dl.pop(0)\n",
    "            if val == \"None\": return None\n",
    "            root = TreeNode(int(val))\n",
    "            root.left = dfs(dl)\n",
    "            root.right = dfs(dl)\n",
    "            return root\n",
    "        ns = data.split(\" \")\n",
    "        return dfs(ns)\n",
    "\n",
    "'''\n",
    "class Codec:\n",
    "    # 层序遍历\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"\"\n",
    "        queue, res = [root], []\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node:\n",
    "                # 这里要转为str是因为后面要对res用join函数\n",
    "                res.append(str(node.val))\n",
    "                # 由于需要考虑每个节点的空节点子树\n",
    "                # 因此不需要对node的左右子树进行判空\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                # 这里要转为str是因为后面要对res用join函数\n",
    "                res.append(str(None))\n",
    "        return \" \".join(res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str（这里接受的结果为serialize的返回值）\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data: return []\n",
    "        ns = data.split(\" \")\n",
    "        # 初始化根节点\n",
    "        root = TreeNode(int(ns[0]))\n",
    "        queue = [root]\n",
    "        # 根据层序遍历的结果恢复二叉树\n",
    "        i = 1\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            # 创建左子树\n",
    "            if ns[i] != \"None\":\n",
    "                node.left = TreeNode(int(ns[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            # 创建右子树\n",
    "            if ns[i] != \"None\":\n",
    "                node.right = TreeNode(int(ns[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "'''    \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return None\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for i in range(length):\n",
    "                cur = queue.pop(0)\n",
    "                if cur == None:\n",
    "                    res.append('None')\n",
    "                    continue\n",
    "                else:\n",
    "                    res.append(str(cur.val))\n",
    "                queue.append(cur.left)\n",
    "                queue.append(cur.right)\n",
    "        return res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        head = TreeNode(int(data[0]))\n",
    "        queue = [head]\n",
    "        point = 1\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            if data[point]!= 'None':\n",
    "                cur.left = TreeNode(int(data[point]))\n",
    "                queue.append(cur.left)\n",
    "            point += 1\n",
    "            if data[point] != 'None':\n",
    "                cur.right = TreeNode(int(data[point]))\n",
    "                queue.append(cur.right)\n",
    "            point += 1\n",
    "        return head\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else :\n",
    "                res.append(\"null\")\n",
    "        return '[' + ','.join(res) + ']'\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\":  return\n",
    "        vals, i = data[1:-1].split(','), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if not root: return '[]'\n",
    "        res = []\n",
    "        stk = [root]\n",
    "        while stk:\n",
    "            i = stk.pop(0)\n",
    "            if i:\n",
    "                res.append(str(i.val))\n",
    "                stk.append(i.left)\n",
    "                stk.append(i.right)\n",
    "            else:\n",
    "                res.append('null')\n",
    "        return '[' + ','.join(res) + ']'\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if data == \"[]\": return\n",
    "        vals, i = data[1:-1].split(','), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "        return \"[\"+\",\".join(res)+\"]\"\n",
    "                \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data ==\"[]\":return\n",
    "        vals = data[1:-1].split(\",\")\n",
    "        i = 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i+=1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i+=1\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if not root: return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else: res.append(\"null\")\n",
    "        return '[' + ','.join(res) + ']'\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if data == \"[]\": return\n",
    "        vals, i = data[1:-1].split(','), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        queue, res = collections.deque(), []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "        return res\n",
    "    \n",
    "    def deserialize(self, data):\n",
    "        if not data:\n",
    "            return []\n",
    "        i = 1\n",
    "        root = TreeNode(int(data[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if data[i] != \"null\":\n",
    "                node.left = TreeNode(int(data[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if data[i] != \"null\":\n",
    "                node.right = TreeNode(int(data[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        # 空指针用'#'表示，节点之间用','分隔\n",
    "        if not root:\n",
    "            return '#'\n",
    "        \n",
    "        leftStr = self.serialize(root.left)\n",
    "        rightStr = self.serialize(root.right)\n",
    "        \n",
    "        # 用前序或者后序来表示，不能用中序\n",
    "        myStr = leftStr + ',' + rightStr + ',' + str(root.val)\n",
    "        return myStr \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def helpdeserialize(nodes):\n",
    "            if not nodes:\n",
    "                return None\n",
    "\n",
    "            # 用后序的顺序反序列化\n",
    "            lastNode = nodes.pop()\n",
    "            if lastNode == '#':\n",
    "                return None\n",
    "\n",
    "            root = TreeNode(int(lastNode))\n",
    "\n",
    "            # 反序列化右子树\n",
    "            root.right = helpdeserialize(nodes)\n",
    "    \n",
    "            # 反序列化左子树\n",
    "            root.left = helpdeserialize(nodes)\n",
    "\n",
    "            return root \n",
    "\n",
    "        # 将 data 转变为列表\n",
    "        nodes = data.split(',')\n",
    "        return helpdeserialize(nodes)   \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"[]\"\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        tmp = []\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node:\n",
    "                tmp.append(str(node.val))\n",
    "                q.append(node.left)\n",
    "                q.append(node.right)\n",
    "            else:\n",
    "                tmp.append(\"null\")\n",
    "        return \"[\" + \",\".join(tmp) + \"]\"\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\": return\n",
    "        q = collections.deque()\n",
    "        vals, i = data[1:-1].split(\",\"), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                q.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                q.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        q = [root]\n",
    "        res = []\n",
    "        while q:\n",
    "            tmp = []\n",
    "            new_res = []\n",
    "            for item in q:\n",
    "                if item is not None:\n",
    "                    tmp.append(item.left)\n",
    "                    tmp.append(item.right)\n",
    "                    new_res.append(str(item.val))\n",
    "                else:\n",
    "                    new_res.append(\"null\")\n",
    "            if all([i is None for i in tmp]):\n",
    "                while new_res and new_res[-1] == \"null\":\n",
    "                    new_res.pop()\n",
    "                res.append(new_res)\n",
    "                break\n",
    "            res.append(new_res)\n",
    "            q = tmp\n",
    "        return \",\".join([\" \".join(item) for item in res])\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"\":\n",
    "            return None\n",
    "        res = data.split(\",\")\n",
    "        root = None\n",
    "        node_list = deque()\n",
    "        for item in res:\n",
    "            item = item.split()\n",
    "            new_node_list = deque()\n",
    "            for val in item:\n",
    "                new_node = TreeNode(int(val)) if val != \"null\" else None\n",
    "                if root is None:\n",
    "                    root = new_node\n",
    "                new_node_list.append(new_node)\n",
    "            if len(node_list) != 0:\n",
    "                index = 0\n",
    "                for node_old in node_list:\n",
    "                    if node_old is None:\n",
    "                        continue\n",
    "                    node_old.left = new_node_list[index]\n",
    "                    index += 1\n",
    "                    if index == len(new_node_list):\n",
    "                        break\n",
    "                    node_old.right = new_node_list[index]\n",
    "                    index += 1\n",
    "                    if index == len(new_node_list):\n",
    "                        break\n",
    "            node_list = new_node_list\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# https://mp.weixin.qq.com/s/DVX2A1ha4xSecEXLxW_UsA\n",
    "# 哦，原来前序遍历的意思是：先遍历根节点，再遍历左子树，最后遍历右子树\n",
    "# 本题考查：已知一个前序遍历结果列表，里面包含了空指针，如何构造一颗二叉树。\n",
    "# 而前面的题是已已知2个序遍历结果，没有空指针信息，如何构建一颗二叉树\n",
    "\n",
    "# 方法一：前序遍历实现的序列化、反序列化方法。掌握这一种方法就行了。其他两种知道下就行了\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        # 用于拼接字符串\n",
    "        self.res = []\n",
    "    \n",
    "    # 先序列化成列表，并带上空指针\n",
    "    # 题目后面有注释说了，ser这个序列化函数的返回结果会自动传递给deser这个函数的\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.traverse(root)\n",
    "\n",
    "        return \"\".join(self.res)\n",
    "    \n",
    "    # 将二叉树打平为字符串\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            # 定义一个常量，表示空节点，也可以定义成常量放进init里\n",
    "            self.res.append(\"#\")\n",
    "            # 定义一个常量，表示分隔符，也可以定义成常量放进init里\n",
    "            self.res.append(\",\")\n",
    "            return\n",
    "        \n",
    "        self.res.append(str(root.val)) # 这里str的原因是：后面会把list转为str，所以list里的元素都必须为str，而不是部分str部分int会报错的\n",
    "        self.res.append(\",\")\n",
    "\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "\n",
    "    # 主函数，将字符串反序列化为二叉树结构\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        # data = \"\".join(self.res)\n",
    "        nodes = data.split(\",\")\n",
    "\n",
    "        return self._deserialize(nodes)\n",
    "    \n",
    "    def _deserialize(self, data):\n",
    "        # 如果列表为空，返回空节点\n",
    "        if not data:\n",
    "            return None\n",
    "\n",
    "        # 前序遍历位置\n",
    "        # 列表最左侧就是根节点\n",
    "        root_val = data.pop(0)\n",
    "        if root_val == \"#\": # 遇见空指针,如果是空节点，返回空节点\n",
    "            return None\n",
    "        root = TreeNode(int(root_val))\n",
    "\n",
    "        # 递归地构造左右子树\n",
    "        root.left = self._deserialize(data)\n",
    "        root.right = self._deserialize(data)\n",
    "\n",
    "        # 返回根节点\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))\n",
    "\n",
    "# 方法二：后序遍历实现的序列化、反序列化方法\n",
    "# class Codec:\n",
    "#     def __init__(self):\n",
    "#         # 用于拼接字符串\n",
    "#         self.res = []\n",
    "    \n",
    "#     # 先序列化成列表，并带上空指针\n",
    "#     # 题目后面有注释说了，ser这个序列化函数的返回结果会自动传递给deser这个函数的\n",
    "#     def serialize(self, root):\n",
    "#         \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "#         :type root: TreeNode\n",
    "#         :rtype: str\n",
    "#         \"\"\"\n",
    "#         self.traverse(root)\n",
    "\n",
    "#         return \"\".join(self.res)\n",
    "    \n",
    "#     # 将二叉树打平为字符串\n",
    "#     def traverse(self, root):\n",
    "#         if not root:\n",
    "#             # 定义一个常量，表示空节点，也可以定义成常量放进init里\n",
    "#             self.res.append(\"#\")\n",
    "#             # 定义一个常量，表示分隔符，也可以定义成常量放进init里\n",
    "#             self.res.append(\",\")\n",
    "#             return\n",
    "\n",
    "#         self.traverse(root.left)\n",
    "#         self.traverse(root.right)\n",
    "#         self.res.append(str(root.val)) # 这里str的原因是：后面会把list转为str，所以list里的元素都必须为str，而不是部分str部分int会报错的\n",
    "#         self.res.append(\",\")\n",
    "\n",
    "#     # 主函数，将字符串反序列化为二叉树结构\n",
    "#     def deserialize(self, data):\n",
    "#         \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "#         :type data: str\n",
    "#         :rtype: TreeNode\n",
    "#         \"\"\"\n",
    "#         nodes = data.split(\",\")\n",
    "\n",
    "#         return self._deserialize(nodes)\n",
    "    \n",
    "#     def _deserialize(self, data):\n",
    "#         # 如果列表为空，返回空节点\n",
    "#         if not data:\n",
    "#             return None\n",
    "\n",
    "#         # 后序遍历位置\n",
    "#         # 列表最右侧就是根节点\n",
    "#         # 这里pop的总是列表最后一个元素。而后序遍历是左子树、右子树、根节点的顺序。\n",
    "#         # 因为pop总的总是最后一个元素，所以pop完根节点之后，就该pop右子树的节点了。所以递归的时候，要先递归右子树，在递归左子树\n",
    "#         root_val = data.pop()\n",
    "#         if root_val == \"#\": # 遇见空指针,如果是空节点，返回空节点\n",
    "#             return None\n",
    "#         root = TreeNode(int(root_val))\n",
    "\n",
    "#         # 递归地构造左右子树\n",
    "#         root.right = self._deserialize(data)\n",
    "#         root.left = self._deserialize(data)\n",
    "        \n",
    "#         # 返回根节点\n",
    "#         return root\n",
    "\n",
    "# # 方法三：层序遍历。我就不写了。也挺好理解的，不用掌握\n",
    "\n",
    "# # 定义一个常量，表示分隔符\n",
    "# SEP = \",\"\n",
    "# # 定义一个常量，表示空节点\n",
    "# NULL = \"#\"\n",
    "\n",
    "# # 定义一个函数，将二叉树序列化为字符串\n",
    "# def serialize(root):\n",
    "#     if root is None: # 如果根节点为空，返回空字符串\n",
    "#         return \"\"\n",
    "#     sb = [] # 定义一个列表，用来存储字符串\n",
    "#     # 初始化队列，将 root 加入队列\n",
    "#     q = [root]\n",
    "    \n",
    "#     while q: # 当队列不为空时，循环执行以下操作\n",
    "#         cur = q.pop(0) # 弹出队列的第一个元素\n",
    "        \n",
    "#         # 层级遍历代码位置\n",
    "#         if cur is None: # 如果当前节点为空\n",
    "#             sb.append(NULL + SEP) # 将空节点的标识符和分隔符加入列表\n",
    "#             continue # 跳过后续操作\n",
    "#         sb.append(str(cur.val) + SEP) # 将当前节点的值和分隔符加入列表\n",
    "#         # 将当前节点的左右子节点加入队列\n",
    "#         q.append(cur.left)\n",
    "#         q.append(cur.right)\n",
    "    \n",
    "#     return \"\".join(sb) # 将列表中的字符串拼接起来，返回结果\n",
    "\n",
    "\n",
    "# # 将字符串反序列化为二叉树结构\n",
    "# def deserialize(data):\n",
    "#     if not data: return None\n",
    "#     nodes = data.split(SEP)\n",
    "#     # 第一个元素就是 root 的值\n",
    "#     root = TreeNode(int(nodes[0]))\n",
    "\n",
    "#     # 队列 q 记录父节点，将 root 加入队列\n",
    "#     q = collections.deque()\n",
    "#     q.append(root)\n",
    "\n",
    "#     i = 1\n",
    "#     while q:\n",
    "#         # 队列中存的都是父节点\n",
    "#         parent = q.popleft()\n",
    "#         # 父节点对应的左侧子节点的值\n",
    "#         left = nodes[i]\n",
    "#         i += 1\n",
    "#         if left != NULL:\n",
    "#             parent.left = TreeNode(int(left))\n",
    "#             q.append(parent.left)\n",
    "#         else:\n",
    "#             parent.left = None\n",
    "#         # 父节点对应的右侧子节点的值\n",
    "#         right = nodes[i]\n",
    "#         i += 1\n",
    "#         if right != NULL:\n",
    "#             parent.right = TreeNode(int(right))\n",
    "#             q.append(parent.right)\n",
    "#         else:\n",
    "#             parent.right = None\n",
    "#     return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        ret=[]\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            node=q.popleft()\n",
    "            if not node:\n",
    "                ret.append('n')\n",
    "            else:\n",
    "                ret.append(str(node.val))\n",
    "                q.append(node.left)\n",
    "                q.append(node.right)\n",
    "        return '#'.join(ret)\n",
    "            \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if len(data)==0:\n",
    "            return None\n",
    "        val_list=data.split('#')\n",
    "        head=TreeNode(int(val_list[0]))\n",
    "        val_list.pop(0)\n",
    "        q=deque()\n",
    "        q.append(head)\n",
    "        while val_list:\n",
    "            node=q.popleft()\n",
    "            l=val_list.pop(0)\n",
    "            r=val_list.pop(0)\n",
    "            if l!='n':\n",
    "                left_node=TreeNode(int(l))\n",
    "                node.left=left_node\n",
    "                q.append(left_node)\n",
    "            if r!='n':\n",
    "                right_node=TreeNode(int(r))\n",
    "                node.right=right_node\n",
    "                q.append(right_node)\n",
    "        return head\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                res.append(\"N\")\n",
    "                return\n",
    "            res.append(str(node.val))\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return \",\".join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        vals = data.split(\",\")\n",
    "        self.i = 0\n",
    "\n",
    "        def dfs():\n",
    "            if vals[self.i] == \"N\":\n",
    "                self.i += 1\n",
    "                return None\n",
    "            node = TreeNode(int(vals[self.i]))\n",
    "            self.i += 1\n",
    "            node.left = dfs()\n",
    "            node.right = dfs()\n",
    "            return node\n",
    "\n",
    "        return dfs()\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            return str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)\n",
    "\n",
    "        res = dfs(root)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return \n",
    "        val = data.split(',')\n",
    "        result = None\n",
    "        stack = []\n",
    "        for x in val:\n",
    "            node = TreeNode(int(x), '', '') if x else None\n",
    "\n",
    "            if not result: # 指向头\n",
    "                result = node\n",
    "            \n",
    "            if stack:\n",
    "                if stack[-1].left == '': # 避免出现None无法跳过的问题\n",
    "                    stack[-1].left = node\n",
    "                else:\n",
    "                    stack[-1].right = node\n",
    "                    stack.pop()\n",
    "            \n",
    "            if node:\n",
    "                stack.append(node)\n",
    "\n",
    "        return result\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.NoneNum = -2 ** 31 - 1\n",
    "\n",
    "    def dfs(self, root):\n",
    "        retList = [root]\n",
    "        path = []\n",
    "        while retList:\n",
    "            midList = []\n",
    "            for node in retList:\n",
    "                if node:\n",
    "                    path.append(node.val)\n",
    "                    if node.left:\n",
    "                        midList.append(node.left)\n",
    "                    else:\n",
    "                        midList.append(None)\n",
    "                    if node.right:\n",
    "                        midList.append(node.right)\n",
    "                    else:\n",
    "                        midList.append(None)\n",
    "                else:\n",
    "                    path.append(self.NoneNum)\n",
    "            retList = midList.copy()\n",
    "        return path\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        retStr = '['\n",
    "        path = self.dfs(root)           \n",
    "        n = len(path) - 1\n",
    "        while n > -1 and path[n] == self.NoneNum:\n",
    "            n -= 1\n",
    "        for i in range(n+1):\n",
    "            if path[i] != self.NoneNum:\n",
    "                retStr = retStr + str(path[i])\n",
    "            else:\n",
    "                retStr = retStr + 'null'\n",
    "            if i != n:\n",
    "                retStr = retStr + ','\n",
    "        retStr = retStr + ']'\n",
    "        return retStr\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        n = len(data)\n",
    "        data = data[1:n-1].split(',')\n",
    "        print(data)\n",
    "        if len(data) == 1 and data[0] == '':\n",
    "            return None\n",
    "        midList = []\n",
    "        for d in data:\n",
    "            if d == 'null':\n",
    "                midList.append(self.NoneNum)\n",
    "            else:\n",
    "                midList.append(int(d))\n",
    "\n",
    "        retNode = TreeNode(0)\n",
    "        root = TreeNode(midList[0])\n",
    "        retNode.left = root\n",
    "        n = len(midList)\n",
    "        ind = 1\n",
    "        midmidList = [root]\n",
    "        while ind < n:\n",
    "            node = midmidList.pop(0)\n",
    "            if midList[ind] == self.NoneNum:\n",
    "                node.left = None\n",
    "            else:\n",
    "                node.left = TreeNode(midList[ind])\n",
    "                midmidList.append(node.left)\n",
    "            ind += 1\n",
    "            if ind >= n:\n",
    "                break\n",
    "            if midList[ind] == self.NoneNum:\n",
    "                node.right = None\n",
    "            else:\n",
    "                node.right = TreeNode(midList[ind])\n",
    "                midmidList.append(node.right)\n",
    "            ind += 1\n",
    "\n",
    "        return retNode.left\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return self.serialize_recursive(root)\n",
    "\n",
    "    def serialize_recursive(self, root) :\n",
    "        if not root:\n",
    "            return \"None\"\n",
    "        return str(root.val) +\",\"+ self.serialize(root.left) +\",\"+ self.serialize(root.right)\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        val_list= data.split(\",\")\n",
    "        return self.deserialize_recursive(val_list)\n",
    "    \n",
    "    def deserialize_recursive(self, val_list):\n",
    "        val = val_list.pop(0)\n",
    "        if val==\"None\":\n",
    "            return None\n",
    "        node = TreeNode(val)\n",
    "        node.left = self.deserialize_recursive(val_list)\n",
    "        node.right = self.deserialize_recursive(val_list)\n",
    "        return node\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \n",
    "        # res = []\n",
    "        # queue = collections.deque()\n",
    "        # queue.append(root)\n",
    "        # # 通过队列的方法遍历二叉树 返回值是：['1', '2', '3', '#', '#', '4', '5', '#', '#', '#', '#']\n",
    "        # while(queue):\n",
    "        #     curs = queue.popleft()\n",
    "        #     if not curs:\n",
    "        #         res.append('#') \n",
    "        #     else:\n",
    "        #         res.append(str(curs.val))\n",
    "        #         queue.append(curs.left)\n",
    "        #         queue.append(curs.right)\n",
    "        # # print(res)   #返回值： ['1', '2', '3', '#', '#', '4', '5', '#', '#', '#', '#']\n",
    "        # print(' '.join(res)) # 123##45####\n",
    "        # return ' '.join(res) \n",
    "\n",
    "        # def deserialize(self, data):\n",
    "        # \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        # :type data: str\n",
    "        # :rtype: TreeNode\n",
    "        # \"\"\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 通过迭代遍历。  前序遍历  中左右 12##34##5##\n",
    "        res = []\n",
    "        def decode(root):\n",
    "            if not root:\n",
    "                res.append('#')\n",
    "            else:\n",
    "                res.append(str(root.val))\n",
    "                decode(root.left)\n",
    "                decode(root.right)\n",
    "        decode(root)\n",
    "        print(' '.join(res))# 用空格作为连接符\n",
    "        return ' '.join(res)\n",
    "\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        # 首先将data分割\n",
    "        # 遍历 按照顺序赋值root,下一个则赋值给左右子树\n",
    "        vals = iter(data.split()) # 用空格分割开\n",
    "        \n",
    "        def decode():\n",
    "            val = next(vals)\n",
    "            if val == '#':\n",
    "                return None\n",
    "            else:\n",
    "                cur = TreeNode(int(val))\n",
    "                cur.left = decode()\n",
    "                cur.right = decode()\n",
    "            return cur\n",
    "        return decode()\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.s = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                self.s.append('N')\n",
    "                return\n",
    "            self.s.append(str(root.val))\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return ','.join(self.s)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        vals = data.split(',')\n",
    "        self.i = 0\n",
    "        def dfs():\n",
    "            if vals[self.i] == 'N':\n",
    "                self.i += 1\n",
    "                return\n",
    "            node = TreeNode(int(vals[self.i]))\n",
    "            self.i += 1\n",
    "            node.left = dfs()\n",
    "            node.right = dfs()\n",
    "            return node\n",
    "        return dfs()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "  def serialize(self, root):\n",
    "    # 用括号框起来\n",
    "    if not root:\n",
    "      return 'X'\n",
    "    return f'({self.serialize(root.left)}){root.val}({self.serialize(root.right)})'\n",
    "\n",
    "  def deserialize(self, data):\n",
    "    n = len(data)\n",
    "    i = 0\n",
    "\n",
    "    def parse():\n",
    "      nonlocal i\n",
    "      if data[i] == 'X':\n",
    "        i += 1\n",
    "        return None\n",
    "      left = parse_tree()\n",
    "      val = parse_int()\n",
    "      right = parse_tree()\n",
    "      return TreeNode(val, left, right)\n",
    "    \n",
    "    def parse_int():\n",
    "      nonlocal i\n",
    "      s = ''\n",
    "      sign = 1\n",
    "      if data[i] == '-':\n",
    "        sign = -1\n",
    "        i += 1\n",
    "      while i < n and data[i].isdigit():\n",
    "        s += data[i]\n",
    "        i += 1\n",
    "      return int(s) * sign\n",
    "    \n",
    "    def parse_tree():\n",
    "      nonlocal i\n",
    "      i += 1  # skip (\n",
    "      tree = parse()\n",
    "      i += 1  # skip )\n",
    "      return tree\n",
    "    \n",
    "    return parse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "\n",
    "        def dfs(node: TreeNode | None, i: int = 0):\n",
    "            if not node:\n",
    "                return\n",
    "            ans.append(str(i))\n",
    "            ans.append(str(node.val))\n",
    "            dfs(node.left, i + i + 1)\n",
    "            dfs(node.right, i + i + 2)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return \",\".join(ans)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return\n",
    "        pairs = data.split(\",\")\n",
    "        i = 0\n",
    "        m = {}\n",
    "        while i < len(pairs):\n",
    "            m[int(pairs[i])] = int(pairs[i + 1])\n",
    "            i += 2\n",
    "\n",
    "        def dfs(i: int) -> TreeNode | None:\n",
    "            if i not in m:\n",
    "                return\n",
    "            node = TreeNode(m[i])\n",
    "            node.left = dfs(i + i + 1)\n",
    "            node.right = dfs(i + i + 2)\n",
    "            return node\n",
    "\n",
    "        return dfs(0)\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import json\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \n",
    "        def s(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            ans={\"val\":root.val}\n",
    "            ans[\"left\"]=s(root.left)\n",
    "            ans[\"right\"]=s(root.right)\n",
    "            return ans\n",
    "        ans=s(root)\n",
    "        return json.dumps(ans)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def d(i):\n",
    "            if not i:\n",
    "                return None\n",
    "            return TreeNode(i[\"val\"],d(i[\"left\"]),d(i[\"right\"]))\n",
    "        i=json.loads(data)\n",
    "        return d(i)\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import collections\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        curr = collections.deque()\n",
    "        if not root:return ''\n",
    "        curr.append(root)\n",
    "        records = collections.deque()\n",
    "        records.append(root)\n",
    "        while curr:\n",
    "            nexts = collections.deque()\n",
    "            for i in range(len(records)):\n",
    "                node = records.popleft()\n",
    "                idex =node.val\n",
    "                self.res.append(str(idex))\n",
    "                if idex!=-1.1:\n",
    "                    if node.left:\n",
    "                        nexts.append(node.left)\n",
    "                        records.append(node.left)\n",
    "                    else: records.append(TreeNode(-1.1))\n",
    "                    if node.right:\n",
    "                        nexts.append(node.right)\n",
    "                        records.append(node.right)\n",
    "                    else: records.append(TreeNode(-1.1))\n",
    "            curr = nexts\n",
    "        return (',').join(self.res)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:return []\n",
    "        lists = data.split(',')\n",
    "        head = TreeNode(lists.pop(0))\n",
    "        pre = head\n",
    "        curr = [head]\n",
    "        while lists:\n",
    "            temp = []\n",
    "            for i in range(len(curr)):\n",
    "                left = lists.pop(0)\n",
    "                right =lists.pop(0)\n",
    "                curr[i].left = self.getnode(left)\n",
    "                curr[i].right = self.getnode(right)\n",
    "                if curr[i].left: temp.append(curr[i].left)\n",
    "                if curr[i].right: temp.append(curr[i].right)\n",
    "            curr = temp\n",
    "        return head\n",
    "\n",
    "                \n",
    "                \n",
    "    def getnode(self,x):\n",
    "        if x!= '-1.1':\n",
    "            x = int(x)\n",
    "            return TreeNode(x)\n",
    "        return None\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        res= []\n",
    "        while queue:\n",
    "            temp = []\n",
    "            for q in queue:\n",
    "                if q:\n",
    "                    res.append(q.val)\n",
    "                    temp.append(q.left)\n",
    "                    temp.append(q.right)\n",
    "                else:\n",
    "                    res.append(\"null\")\n",
    "            queue = temp\n",
    "            if queue == [None]*len(queue):\n",
    "                break\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        j = 0\n",
    "        root = TreeNode(data[j])\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            temp = []\n",
    "            for q in queue:\n",
    "                if q:\n",
    "                    if j+1 < len(data):\n",
    "                        q.left = TreeNode(data[j+1])\n",
    "                        temp.append(q.left)\n",
    "                    if j+2 < len(data):\n",
    "                        q.right = TreeNode(data[j+2])\n",
    "                        temp.append(q.right)\n",
    "                    j = j+2\n",
    "            queue = temp\n",
    "        return root\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import collections\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        curr = collections.deque()\n",
    "        if not root:return ''\n",
    "        curr.append(root)\n",
    "        records = collections.deque()\n",
    "        records.append(root)\n",
    "        while curr:\n",
    "            nexts = collections.deque()\n",
    "            for i in range(len(records)):\n",
    "                node = records.popleft()\n",
    "                idex =node.val\n",
    "                self.res.append(str(idex))\n",
    "                if idex!=-1.1:\n",
    "                    if node.left:\n",
    "                        nexts.append(node.left)\n",
    "                        records.append(node.left)\n",
    "                    else: records.append(TreeNode(-1.1))\n",
    "                    if node.right:\n",
    "                        nexts.append(node.right)\n",
    "                        records.append(node.right)\n",
    "                    else: records.append(TreeNode(-1.1))\n",
    "            curr = nexts\n",
    "        return (',').join(self.res)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:return []\n",
    "        lists = data.split(',')\n",
    "        head = TreeNode(lists.pop(0))\n",
    "        pre = head\n",
    "        curr = [head]\n",
    "        while lists:\n",
    "            temp = []\n",
    "            for i in range(len(curr)):\n",
    "                left = lists.pop(0)\n",
    "                right =lists.pop(0)\n",
    "                curr[i].left = self.getnode(left)\n",
    "                curr[i].right = self.getnode(right)\n",
    "                if curr[i].left: temp.append(curr[i].left)\n",
    "                if curr[i].right: temp.append(curr[i].right)\n",
    "            curr = temp\n",
    "        return head\n",
    "\n",
    "                \n",
    "                \n",
    "    def getnode(self,x):\n",
    "        if x!= '-1.1':\n",
    "            x = int(x)\n",
    "            return TreeNode(x)\n",
    "        return None\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.output =[]\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                self.output.append(str(node.val))\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "            else:\n",
    "                self.output.append('null')\n",
    "            \n",
    "\n",
    "        if not root: return ''\n",
    "        dfs(root)\n",
    "        return ','.join(self.output)\n",
    "                \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == '':\n",
    "            return\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            if data[self.i]!='null':\n",
    "                val = int(data[self.i])\n",
    "                node.left = TreeNode(val)\n",
    "                self.i+=1\n",
    "                dfs(node.left)\n",
    "            else:\n",
    "                node.left = None\n",
    "                self.i +=1\n",
    "            if data[self.i] !='null':\n",
    "                val = int(data[self.i])\n",
    "                node.right = TreeNode(val)\n",
    "                self.i+=1\n",
    "                dfs(node.right)\n",
    "            else:\n",
    "                node.right = None\n",
    "                self.i +=1\n",
    "\n",
    "        self.i =1\n",
    "        data = data.split(',')\n",
    "        root = TreeNode(int(data[0]))\n",
    "        dfs(root)\n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "#序列化可以采用后序遍历+前序/中序遍历，通过dfs找根，左子树根，右子树根来反序列化\n",
    "#序列化也可以采用层序遍历序，通过bfs反序列化\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def bfs(x):\n",
    "            if not x: return []\n",
    "            ans,queue=[],collections.deque()\n",
    "            queue.append(x)\n",
    "            while queue:\n",
    "                cur=queue.popleft()\n",
    "                if cur:                     #这里的层序遍历和之前写的有区别，因为要存储null占位置，方便后面反序列化\n",
    "                    ans.append(cur.val)\n",
    "                else:\n",
    "                    ans.append(None)\n",
    "                    continue\n",
    "                queue.append(cur.left)\n",
    "                queue.append(cur.right)\n",
    "            return ans\n",
    "        return bfs(root)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        print(data)\n",
    "        if data==[]: return None\n",
    "        \n",
    "        root=TreeNode(data[0])\n",
    "        queue=collections.deque()\n",
    "        queue.append(root)\n",
    "        index=1\n",
    "\n",
    "        while queue:\n",
    "            cur=queue.popleft()\n",
    "            if not cur: continue\n",
    "            new=TreeNode(data[index]) if data[index] != None else None  #不能直接if data[index]，这样data[index]=0时也会被当作None\n",
    "            cur.left=new\n",
    "            queue.append(new)\n",
    "            index+=1\n",
    "\n",
    "            new=TreeNode(data[index]) if data[index] != None else None\n",
    "            cur.right=new\n",
    "            queue.append(new)\n",
    "            index+=1\n",
    "        print(root)\n",
    "        return root\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        tree = ''\n",
    "        if(root==None):\n",
    "            return tree\n",
    "        import queue\n",
    "        out_q = queue.Queue()\n",
    "        out_q.put(root)\n",
    "        while(not out_q.empty()):\n",
    "            out = out_q.get()\n",
    "            if(out!=None):\n",
    "                tree = tree + ' '+ str(out.val)\n",
    "                if(out.left!=None):\n",
    "                    out_q.put(out.left)\n",
    "                else:\n",
    "                    out_q.put(None)\n",
    "                if(out.right!=None):\n",
    "                    out_q.put(out.right)\n",
    "                else:\n",
    "                    out_q.put(None)    \n",
    "            else:\n",
    "                tree = tree + ' null'\n",
    "        return tree\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if(data==''):\n",
    "            return None\n",
    "        data = data.split(' ')[1:]\n",
    "        # print(data)\n",
    "        root = TreeNode()\n",
    "        import queue\n",
    "        int_q = queue.Queue()\n",
    "        int_q.put(root)\n",
    "        m = len(data)\n",
    "        for i in range(m):\n",
    "            out = int_q.get()\n",
    "            if(data[i]!='null'):\n",
    "                out.val = data[i]\n",
    "                out.left = TreeNode()\n",
    "                out.right = TreeNode()\n",
    "                int_q.put(out.left)\n",
    "                int_q.put(out.right)\n",
    "            else:\n",
    "                out.val = 'null'\n",
    "        \n",
    "        int_q.put(root)\n",
    "        while(not int_q.empty()):\n",
    "            temp = int_q.get()\n",
    "            if(temp.left.val=='null'):\n",
    "                temp.left=None\n",
    "            else:\n",
    "                int_q.put(temp.left)\n",
    "            if(temp.right.val=='null'):\n",
    "                temp.right=None\n",
    "            else:\n",
    "                int_q.put(temp.right)\n",
    "        \n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "\n",
    "        if not root:\n",
    "            return \"n\"\n",
    "\n",
    "        res = str(root.val)\n",
    "        res += 'l' + self.serialize(root.left)\n",
    "        res += 'r' + self.serialize(root.right)\n",
    "        return res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"n\":\n",
    "            return None\n",
    "        i = data.index('l')\n",
    "\n",
    "        left = 1\n",
    "        right = 0\n",
    "        n = len(data)\n",
    "        for j in range(i+1, n):\n",
    "            left += int(data[j]=='l')\n",
    "            right += int(data[j]=='r')\n",
    "            if left == right:\n",
    "                break\n",
    "        root = TreeNode(int(data[:i]))\n",
    "        root.left = self.deserialize(data[i+1:j])\n",
    "        root.right = self.deserialize(data[j+1:])\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return ''\n",
    "        return str(root.val)+'('+self.serialize(root.left)+' '+self.serialize(root.right)+')'\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data: return None\n",
    "        if ' ' not in data: return TreeNode(int(data))\n",
    "        a = 0\n",
    "        while a<len(data) and data[a] != '(':\n",
    "            a += 1\n",
    "        root = TreeNode(int(data[:a]))\n",
    "        b = a+1\n",
    "        depth = 0\n",
    "        for b in range(a+1,len(data)):\n",
    "            if data[b] == '(': depth += 1\n",
    "            elif data[b] == ')': depth -= 1\n",
    "            elif data[b] == ' ' and depth == 0: break\n",
    "        root.left = self.deserialize(data[a+1:b])\n",
    "        root.right = self.deserialize(data[b+1:-1])\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "\n",
    "        if not root:\n",
    "            return \"n\"\n",
    "\n",
    "        res = str(root.val)\n",
    "        res += 'l' + self.serialize(root.left)\n",
    "        res += 'r' + self.serialize(root.right)\n",
    "        return res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"n\":\n",
    "            return None\n",
    "        i = data.index('l')\n",
    "\n",
    "        left = 1\n",
    "        right = 0\n",
    "        n = len(data)\n",
    "        for j in range(i+1, n):\n",
    "            left += int(data[j]=='l')\n",
    "            right += int(data[j]=='r')\n",
    "            if left == right:\n",
    "                break\n",
    "        root = TreeNode(int(data[:i]))\n",
    "        root.left = self.deserialize(data[i+1:j])\n",
    "        root.right = self.deserialize(data[j+1:])\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return 'n'\n",
    "        res = str(root.val) \n",
    "        res += 'l' + self.serialize(root.left)\n",
    "        res += 'r' + self.serialize(root.right)\n",
    "        return res   \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == 'n': return\n",
    "        i = data.index('l')\n",
    "        left = 1\n",
    "        right = 0\n",
    "        n = len(data)\n",
    "        for j in range(i+1, n):\n",
    "            left += int(data[j] == 'l')\n",
    "            right += int(data[j] == 'r')\n",
    "            if left == right:\n",
    "                break\n",
    "        root = TreeNode(data[:i])\n",
    "        root.left = self.deserialize(data[i+1:j])\n",
    "        root.right = self.deserialize(data[j+1:])\n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None: return '[]'\n",
    "        res = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack.pop(0)\n",
    "            res.append(str(cur.val) if cur else 'null')\n",
    "            if cur:\n",
    "                stack.append(cur.left)\n",
    "                stack.append(cur.right)\n",
    "\n",
    "        while res[-1] is None:\n",
    "            res.pop()\n",
    "        return '[' + ','.join(res) + ']'\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if len(data)<3: return None\n",
    "        node_list = data[1:-1].split(',')\n",
    "        root = TreeNode(node_list[0])\n",
    "        cur_layer, i = [root], 1\n",
    "        while cur_layer and i<len(node_list):\n",
    "            cur = cur_layer.pop(0)\n",
    "            if node_list[i]:\n",
    "                cur.left = TreeNode(node_list[i])\n",
    "                cur_layer.append(cur.left)\n",
    "            i+=1\n",
    "            if i<len(node_list) and node_list[i]:\n",
    "                cur.right = TreeNode(node_list[i])\n",
    "                cur_layer.append(cur.right)\n",
    "            i+=1\n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return '[]'\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            if not queue[0]: res.append('null')\n",
    "            else:\n",
    "                res.append(str(queue[0].val))\n",
    "                queue.append(queue[0].left)\n",
    "                queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        return '['+','.join(res)+']'\n",
    "                \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        data = data[1:-1]\n",
    "        if not data: return None\n",
    "        data = data.split(',')\n",
    "        length = len(data)\n",
    "        node_list = []\n",
    "        null_num = 0\n",
    "        for i in data:\n",
    "            if i == 'null': \n",
    "                null_num += 1\n",
    "                node_list.append([None, null_num])\n",
    "            else: node_list.append([TreeNode(int(i)), null_num])\n",
    "        head = node_list[0][0]\n",
    "        for i in range(length):\n",
    "            if 2 * (i - node_list[i][1] + 1) < length and node_list[i][0]:\n",
    "                node_list[i][0].left = node_list[2 * (i - node_list[i][1]) + 1][0]\n",
    "                node_list[i][0].right = node_list[2 * (i - node_list[i][1] + 1)][0]\n",
    "        return head\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
